//
// Created by Vincent_Vic on 2020/3/30.
//

#ifndef DATAORGANIZATION_MAXHEAP_H
#define DATAORGANIZATION_MAXHEAP_H

#include <algorithm>
#include <cassert>

template <typename Item>
class MaxHeap {
private:
    Item* data;
    int count ;
    int capacity;

    void shiftUp(int k){
        while( k> 1 && data [k / 2] < data[k]){ //判断父节是否小于k节点
            std::swap(data[k/2], data[k]); //调整位置
            k /= 2 ; //进入父节点继续检查调整后的父节点
        }
    }

    void shiftDown(int k){
        while( 2*k <= count){ //判断是否有左孩子就说明可以继续判断
            // 在此轮循环中，data[k]和data[j]交换位置
            // 初始化为父节点与左孩子交换位置j
            int j = 2 * k;
            //右孩子存在并且大于父节点，交换位置j改成右孩子
            if(j + 1 <= count && data[j+1] > data[j]) j ++;
            //如果父节点大于等于要交换的节点，那么无需操作
            if( data[k] >= data[j] ) break;
            std::swap(data[k], data[j]); //调整位置
            k = j ; //进入子节点继续检查调整后的子节点
        }
    }

public:

    MaxHeap(int capacity){
        this->capacity = capacity;
        data = new Item[capacity + 1];
        count = 0;
    }

    //Heapify版本
    MaxHeap(Item arr[],int n){
        data = new Item[n+1];
        count = capacity = n;
        for (int i = 0; i < n; ++i)
            data[i+1] = arr[i];
        for (int i = count / 2; i >= 1 ; --i)
            shiftDown(i);
    }

    virtual ~MaxHeap() {
        delete[] data;
        data = nullptr ;
    }

    int size(){
        return count;
    }

    int getCapacity(){
        return capacity;
    }

    bool isEmpty(){
        return count == 0 ;
    }

    bool insert(Item item){
        if( capacity == count)
            return false; //堆满这里false,也可以可以开辟新的空间
        data[++count] = item; //插入元素
        //调整位置
        shiftUp(count);
        return true;
    }

    Item extractMax(){
        assert( count > 0); //防止二叉堆中没有数据
        Item ret = data[1]; //取出最大值
        std::swap(data[1],data[count--]); //将最后一个元素移动到队首
        shiftDown(1); //向下调整
        return ret;
    }
};


#endif //DATAORGANIZATION_MAXHEAP_H
